package 中等.二分查找;

import java.util.Arrays;
import java.util.Random;

/**
 * 给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi]
 * 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角点。
 * 设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被
 * 矩形覆盖。所有满足要求的点必须等概率被返回。
 * 在给定的矩形覆盖的空间内的任何整数点都有可能被返回。
 * 请注意 ，整数点是具有整数坐标的点。
 * 实现 Solution 类:
 * Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
 * int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/random-point-in-non-overlapping-rectangles
 */
public class 非重叠矩形中的随机点_497 {

    public static void main(String[] args) {

        int[][] rects = {{-2, -2, 1, 1}, {2, 2, 4, 6}};
        Solution solution = new Solution(rects);
        System.out.println(Arrays.toString(solution.pick()));

    }

}

/**
 * 前缀和+二分查找
 * 可能有多个矩阵，里面的点的数量是不一样的，所以不能直接随机选择矩阵
 * 每个矩阵点的个数 (xi-ai+1)*(yi-bi+1)
 * 可以用一个数组 prefixSum[i] 代表前 i 个矩阵里面一共有多少个点，到最后算出
 * 了所有矩阵总共有多少个点，随机函数取一个值，用二分查找确定第 j 个点位于
 * 哪个矩阵 prefixSum[i] >= j ，中取 i 最小的位置，就是位于 i 位置的矩阵里面
 * 随机取矩阵的长 和 宽，得到一个随机点
 */
class Solution {

    private int[][] rects_;

    private int[] prefixSum;

    private Random random = new Random();

    public Solution(int[][] rects) {
        rects_ = rects;
        prefixSum = new int[rects.length];
        int[] rect = rects[0];
        prefixSum[0] = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
        for (int i = 1; i < prefixSum.length; i++) {
            int[] curRect = rects[i];
            prefixSum[i] = prefixSum[i - 1] + (curRect[2] - curRect[0] + 1) * (curRect[3] - curRect[1] + 1);
        }
    }

    public int[] pick() {
        int num = random.nextInt(prefixSum[prefixSum.length - 1]) + 1;
        int left = 0, right = prefixSum.length - 1, target = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (prefixSum[mid] >= num) {
                target = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        int[] targetRect = rects_[target];
        int x = random.nextInt(targetRect[2] - targetRect[0] + 1);
        int y = random.nextInt(targetRect[3] - targetRect[1] + 1);
        return new int[]{targetRect[0] + x, targetRect[1] + y};
    }

}